package com.str.PQ;
public class HeapPriorityQueue implements PriorityQueue {
	
  private static final int DEFAULT_SIZE = 10;
  private Comparable[] array; // The heap array
  private int count;
  
// Constructor
  public HeapPriorityQueue() {   
    array = new Comparable[DEFAULT_SIZE];
    count = 0;
  }

// Modifiers
  public void clear() {
    for (int i = 0; i < count; i++)
      array[i] = null;
    count = 0;	
  }

  public void add(Comparable val) {
    if (count == array.length) expand();
    int curr = count++;
    while (curr > 0) {
      int parent = (curr - 1) / 2;
      if (val.compareTo(array[parent]) > 0)       
        break;
      array[curr] = array[parent];
      curr = parent;
    }
    array[curr] = val;
  }

  public Comparable removeMin() {
  	if (count == 0) 
  	  throw new IllegalStateException();
    Comparable min = array[0];
    Comparable last = array[--count];
    array[count] = null;
    int child, curr = 0;
    while ((child = 2 * curr + 1) < count) {
      if (child + 1 < count && array[child + 1].compareTo(array[child]) < 0)
        child++;
      if (last.compareTo(array[child]) <= 0)
        break;
      array[curr] = array[child];
      curr = child;
    }
    array[curr] = last;
    return min;
  }

// Accessors 
  public boolean isEmpty()
  { return count == 0; }

  public int size()
  { return count; }
 
  public Comparable getMin() {
    if (count == 0) 
      throw new IllegalStateException();
    // else
    return array[0];
  }
 
// Auxiliary methods 
  private void expand() {
  	Comparable[] newArray = new Comparable[2 * array.length];
  	for (int i = 0; i < array.length; i++)
  	  newArray[i] = array[i];
  	array = newArray;
  }
  
  public String toString() {
  	String buf = ""; 
    int i=0, j=1, k=0;
    while (i < count) {
      if (k < j) {      
        buf += array[i++] + " ";
        k++;
      }
      else {
      	buf += "\n";
        k = 0;
        j *= 2;
      }        
    }
    return buf;
  } 
}
